package ArrayAndString;

import java.util.ArrayList;
import java.util.Collections;

public class Array_3 {
    /**
     * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：mat =  [[1,2,3],
     * [4,5,6],
     * [7,8,9]]
     * 输出：[1,2,4,7,5,3,6,8,9]
     * <p>
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length;
        int column = mat[0].length;

        int k = 0;
        int[] resultArray = new int[row * column];

        for (int i = 0; i < row + column - 1; i++) {
            ArrayList<Integer> tempList = new ArrayList<>();
            int r = i < column ? 0 : i - column + 1;
            int c = i < column ? i : column - 1;
            while (r < row && c > -1) {
                tempList.add(mat[r][c]);
                r++;
                c--;
            }
            if (i % 2 == 0) {
                Collections.reverse(tempList);
            }
            for (Integer integer : tempList) {
                resultArray[k++] = integer;
            }
        }
        return resultArray;
    }

    public static void main(String[] args) {
        int[][] ints = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] diagonalOrder = findDiagonalOrder(ints);
        for (int i : diagonalOrder) {
            System.out.println(i);
        }
    }
}
